/*
*    Phantom v2.0 GUI Automation Software
*    Copyright (C) 2009  John C. Van Arsdall (john@phantomtest.com)
*
*    This program is free software; you can redistribute it and/or modify
*    it under the terms of the GNU General Public License as published by
*    the Free Software Foundation; either version 2 of the License, or
*    (at your option) any later version.
*
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU General Public License for more details.
*
*    You should have received a copy of the GNU General Public License along
*    with this program; if not, write to the Free Software Foundation, Inc.,
*    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*
*/
//#include "ssi_defines.h"

#ifndef __TNODE_H__
#define __TNODE_H__


#pragma warning( disable : 4251 )  // Disable warning messages
// This warning is issued when the template is not exported...
// Exported templates dont seem to work in GCC
// Doesnt seem to cause problem (other than warning here)

/*  To be used in a list, a class/variable must be able to do the
    the following:
     1.  Copy constructor
     2.  Equal Operator
     3.  Comparison Operator

*/

template<class aType>
class /*_declspec(dllexport)*/ TNode
{
public:
  TNode();
  ~TNode();
  void Get(aType& In);
  TNode &operator=(TNode& Other);
  char operator==(const TNode& Other);
  char isEqual(const TNode& Other);
  aType operator*();
  TNode* operator++();

  TNode* Set(aType &inData, TNode* inPar = 0, TNode* inNext = 0, TNode* inPrev = 0, TNode* inFChild = 0); 
  TNode* next();
  TNode* prev();
  TNode* par();

  void setNext(TNode* New);
  void setPrev(TNode* New);
  void setPar(TNode* New);
	void setFChild(TNode* New);

  aType& GetData();

  TNode* fchild();

protected:
public:
  TNode* Next;
  TNode* Par;
  TNode* FChild;
  TNode* Prev;
private:
  aType Data;
};

template<class aType>
TNode<aType>::TNode()
{
  Next = 0;
  Par = 0;
  FChild = 0;
  Prev = 0;
}

template<class aType>
TNode<aType>::~TNode()
{
}

template<class aType>
aType& TNode<aType>::GetData()
{
  return Data;
}

template<class aType>
TNode<aType>& TNode<aType>::operator=(TNode& Other)
{
  Next = 0;
  Par = 0;
  FChild = 0;
  Prev = 0;
  Data = Other.Data;
  return *this;
}

template<class aType>
char TNode<aType>::isEqual(const TNode &Other)
{
  if(Data == Other.Data)
  {
    return 1;
  }
  return 0;
}

template<class aType>
aType TNode<aType>::operator*()
{
  return Data;
}

template<class aType>
TNode<aType>* TNode<aType>::operator++()
{
  this = Next;
  return this;
}


template<class aType>
char TNode<aType>::operator==(const TNode &Other)
{
  return isEqual(Other);
}

template<class aType>
void TNode<aType>::setNext(TNode* New)
{
  Next = New;
}

template<class aType>
void TNode<aType>::setPar(TNode* New)
{
  Par = New;
}

template<class aType>
void TNode<aType>::setPrev(TNode* New)
{
  Prev = New;
}

template<class aType>
void TNode<aType>::setFChild(TNode* New)
{
  FChild = New;
}

template<class aType>
void TNode<aType>::Get(aType& In)
{
  In = Data;
}

template<class aType>
TNode<aType>* TNode<aType>::next()
{
  return Next;
}

template<class aType>
TNode<aType>* TNode<aType>::prev()
{
  return Prev;
}

template<class aType>
TNode<aType>* TNode<aType>::par()
{
  return Par;
}

template<class aType>
TNode<aType>* TNode<aType>::fchild()
{
  return FChild;
}

template<class aType>
TNode<aType>* TNode<aType>::Set(aType &inData, TNode* inPar, TNode* inNext, TNode* inPrev, TNode* inFChild)
{
  if(inNext)    Next = inNext;
  if(inPar)     Par = inPar;
  if(inFChild)  FChild = inFChild;
  if(inPrev)    Prev = inPrev;
  Data = inData;
  return this;
}

////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////

#define SSI_Node TNode<aType>

template<class aType>
class	/*_declspec(dllexport)*/ TNodeTree
{
public:
	TNodeTree();
  ~TNodeTree();
  SSI_Node* add(aType& inData, SSI_Node* Par);
  SSI_Node* push(aType& inData);
  char pop(aType& inData);
  SSI_Node* find(aType &inData, SSI_Node* First = 0);	
	int indexof(TNode<aType> *InNode);

	int clear_range(SSI_Node* First, SSI_Node* Last);
	SSI_Node* insert_after(aType &inData, SSI_Node* Before);
	SSI_Node* insert_before(aType &inData, SSI_Node* After);

  SSI_Node* getTop();
  //aType operator[](SSI_INT64 Index);
  SSI_Node* operator[](int Index);
  TNodeTree &operator=(TNodeTree& Other);
  void Clear();
  void remove(SSI_Node* In);
  void sort();
  SSI_Node* add_sort(aType& inData);
  SSI_Node* extract(SSI_Node* In);
protected:
private:
  void clear(SSI_Node* In);
  void copyTree(SSI_Node* Par, SSI_Node* toCopy);
  SSI_Node* Top;
};

template<class aType>
SSI_Node* TNodeTree<aType>::add_sort(aType &inData)
{
  aType Temp;
  SSI_Node* LocTop;
  SSI_Node* add;
  if(Top == 0){
    Top = new SSI_Node;
    Top->Set(inData);
    return Top;
  }else{
    LocTop = Top;
  }

  
  while(LocTop){
    if(inData < LocTop->GetData()){
      add = new SSI_Node;
      add->Set(inData, 0, LocTop, LocTop->Prev, 0);
      if(LocTop->Prev){
        LocTop->Prev->Next = add;
      }else{
        Top = add;
      }
	    LocTop->Prev = add;
      return add;
    }else if(LocTop->Next == SSI_NULL){
      break;
    }else{
      LocTop = LocTop->Next;
    }
  }

  add = new SSI_Node;
  add->Set(inData, 0, 0, LocTop, 0);
  LocTop->Next = add;
  return add;
}


template<class aType>
void TNodeTree<aType>::sort()
{
  /*
  SSI_Node* Move;
  SSI_Node* NewTop = SSI_NULL;
  SSI_Node* LocTop;
  SSI_Node* Curr = Top;

  Curr = extract(Curr);
  NewTop = Curr;
  Curr = Curr->Next; 
  NewTop->Next = NULL;
  
  SSI_BOOL bADDED = 0;

  while(Curr){
    LocTop = NewTop;
    bADDED = 0;
    while(LocTop){
      // Equality Check
      if(Curr->GetData() < LocTop->GetData()){
        // Remove the current node
        Curr = extract(Curr);
        Move = Curr;
        Curr = Curr->Next;
        bADDED = 1;
        printf("%x\n", Curr);

        // Place the current search node before the check node,
        // or at the beginning if there is no parent
        if(LocTop->Prev){
          LocTop->Prev->Next = Move;
          Move->Next = LocTop;
        }else{
          Move->Next = LocTop;
          LocTop->Prev = Move;
          NewTop = Move;
          Move->Prev = SSI_NULL;
        }
        LocTop = SSI_NULL;  // Force advance to next node
      // Advance the CheckNode
      }else{
        LocTop = LocTop->next();
      }
    }
    if(bADDED == 0){
      LocTop = NewTop;
      while(LocTop->Next){
        LocTop = LocTop->Next;
      }
      Curr = extract(Curr);
      Move = Curr;
      Curr = Curr->Next;
      LocTop->Next = Move;
      Move->Next = SSI_NULL;
    }
    // Advance to next node, untill all nodes have been processed.
    //Curr = Curr->Next;
  }
  Top = NewTop;
  */
}

template<class aType>
SSI_Node* TNodeTree<aType>::extract(SSI_Node* In){
  if(In->Prev){
    In->Prev->Next = In->Next;
  }else{
    Top = In->Next;
  }
  if(In->Next){
    In->Next->Prev = In->Prev;
  }
  if(In->Par){
    if(In->Par->FChild == In){
      In->Par->FChild = In->Next;
    }
  }
  return In;
}

template<class aType>
void TNodeTree<aType>::Clear()
{
  clear(Top);
  Top = 0;
}

template<class aType>
TNodeTree<aType> &TNodeTree<aType>::operator=(TNodeTree& Other)
{
  //SSI_Node* OtherTop = Other.Top;
  clear(Top);
  Top = 0;
  copyTree(0, Other.Top);
  return *this;

}

template<class aType>
void TNodeTree<aType>::copyTree(SSI_Node* Par, SSI_Node* toCopy)
{
	if(!toCopy){
		return;
	}
  SSI_Node* copyTemp = toCopy;
  SSI_Node* Ret = 0;
	aType aTemp;
  while(copyTemp)
  {
    copyTemp->Get(aTemp);
    Ret = add(aTemp, Par);
		copyTree(Ret, copyTemp->FChild);
		copyTemp = copyTemp->Next;
  }
}

template<class aType>
SSI_Node* TNodeTree<aType>::operator[](int Index)
{
  int i = 0;
  SSI_Node* Pos = Top;
  while(Pos)
  {
    if(i == Index) return Pos;
    i++;
		if(Pos->Next){
			Pos = Pos->Next;
		}else{
			if(Index == -1){
				return Pos;
			}else{
				return 0;
			}
		}
    
  }
  return 0;
}

template<class aType>
TNodeTree<aType>::TNodeTree()
{
  Top = 0;
}

template<class aType>
TNodeTree<aType>::~TNodeTree()
{
  clear(Top);
}

template<class aType>
SSI_Node* TNodeTree<aType>::add(aType &inData, SSI_Node* Par)
{
  SSI_Node* locFirst;
  SSI_Node* add;
  //SSI_Node* aPar = 0;
  //SSI_Node* aNext = 0;
  //SSI_Node* aFChild = 0;

  aType aTemp;

  if(Par == 0)
  {
    return push(inData);
  }
  else
  {
    if(Par->FChild)
    {
			locFirst = Par->FChild;
    }
    else
    {
      add = new SSI_Node;
      add->Set(inData, Par);
			Par->FChild = add;
      //Par->Get(aTemp);
      //Par->Set(aTemp, Par->par(), Par->next(), Par->prev(), add);
      return add;
    }    
  }

	while(locFirst->Next)
  {
    locFirst = locFirst->Next;
  }
  add = new SSI_Node;
  add->Set(inData, locFirst->par(), 0, locFirst, 0);
	locFirst->Next = add;
  //locFirst->Get(aTemp);
  //locFirst->Set(aTemp, locFirst->par(), add, locFirst->prev(), locFirst->fchild());   
  return add;
}

template<class aType>
SSI_Node* TNodeTree<aType>::insert_after(aType &inData, SSI_Node* Before)
{
  SSI_Node* add;

	if(!Before){
		return 0;
	}

	add = new SSI_Node;
	add->Set(inData, Before->par(), Before->next(), Before, 0);
	if(Before->next()){
		Before->next()->setPrev(add);
	}
	Before->setNext(add);

	return add;
}

template<class aType>
SSI_Node* TNodeTree<aType>::insert_before(aType &inData, SSI_Node* After)
{
  SSI_Node* add;

	if(!After){
		return 0;
	}

	add = new SSI_Node;
	add->Set(inData, After->par(), After, After->prev(), 0);

	if(After->prev()){
		After->prev()->setNext(add);
	}

	After->setPrev(add);
	if(After == Top){
		Top = add;
	}

	return add;
}

template<class aType>
SSI_Node* TNodeTree<aType>::push(aType &inData)
{
  aType Temp;
  SSI_Node* locTop;
  SSI_Node* add;
  if(Top == 0){
    Top = new SSI_Node;
    Top->Set(inData);
    return Top;
  }else{
    locTop = Top;
  }
  while(locTop->Next){
    locTop = locTop->Next;
  }
  add = new SSI_Node;
  add->Set(inData, 0, 0, locTop, 0);
	locTop->Next = add;
	//locTop->Get(Temp);
  //locTop->Set(Temp, locTop->par(), add, locTop->prev(), locTop->fchild());
  return add;
}

template<class aType>
char TNodeTree<aType>::pop(aType& inData)
{

  aType Temp;

  if(Top == 0) return 0;

  SSI_Node* locTop = Top;
  SSI_Node* locPar = 0;
  while(locTop->next())
  {
    locTop = locTop->next();
  }

  locTop->Get(inData);
  locPar = locTop->prev();
  if(locPar)
  {
    locPar->Get(Temp);
    locPar->Set(Temp, locPar->par());
    locPar->setNext(0);
    clear(locTop);
  }
  else
  {
		clear(Top);
    Top = 0;
  }
  
  return 1;
}

template<class aType>
void TNodeTree<aType>::remove(SSI_Node* In)
{
  clear(In);
}


template<class aType>
void TNodeTree<aType>::clear(SSI_Node* In)
{
	// This recursion causes a stack overflow...
	SSI_Node* Temp;
	SSI_Node* TempNext = 0;
	SSI_Node* TempChild = 0;

  if(In == 0) return;
	Temp = In;
	while(Temp){
		TempNext = Temp->Next;
		TempChild = Temp->FChild;
		delete Temp;
		clear(TempChild);
		Temp = TempNext;
	}	
  //if(Temp = In->fchild())
  //{
	//	TempNext = Temp->fchild();
  //  clear(In->fchild());
  //}
  //if(In->next())
  //{
  //  clear(In->next());
  //}
  //if(In) delete(In);
  //In = 0;
}

template<class aType>
int TNodeTree<aType>::clear_range(SSI_Node* First, SSI_Node* Last)
{
	if(!First) return 0;
	if(!Last) return 0;
	if(First->par() != Last->par()){
		return 0;
	}

	SSI_Node* Curr = First;
	SSI_Node* Par = 0;
	SSI_Node* Prev = First->prev();
	SSI_Node* Next = Last->next();
	SSI_Node* Temp;

	while(Curr){
		if(Curr == Last){
      //aType A;
      //pop(A);
      //Prev->Next = SSI_NULL;
      //Last = Prev;
      //return 1;
      break;  //USED TO BE ONLY THIS
		}else{
			Temp = Curr;
			if(Curr->fchild()){
				clear(Curr->fchild());					
			}
 			Curr = Curr->next();

			// Make sure that if you parents first child, clear it...
			if(Temp->par()){
				if(Temp = Temp->par()->fchild()){
					Temp->par()->setFChild(0);
				}
			}

			// Make sure that if you delete Top, clear it...
			if(Temp == Top){
				Top = 0;
			}


			delete Temp;

		}
	}

	if(Curr != Last){
		return 0;
	}

	if(Last->fchild()){
		clear(Last->fchild());					
	}
	if(Last == Top){
		Top = 0;
	}
	delete Last;
		
	if(Prev){
		Prev->setNext(Next);
	}else{
		if(Next){
			Par = Next->par();
			if(Par){
				clear(Par->fchild());
				Par->setFChild(Next);
			}else{
				if(Top){
					clear(Top);
				}
				Top = Next;
			}
		}
	}
	if(Next){
		Next->setPrev(Prev);
	}
  return 1;
}



template<class aType>
int TNodeTree<aType>::indexof(TNode<aType> *InNode)
{
	int ctr = 0;
  SSI_Node* loc;
//SSI_Node* Temp;
  //aType aTemp;

	loc = Top;
	while(loc){
		if(loc == InNode) return ctr;
    //loc->Get(aTemp);
    //if(aTemp == inData) return ctr;
    loc = loc->next();
		ctr++;
	}
	return -1;
}

template<class aType>
SSI_Node* TNodeTree<aType>::find(aType &inData, SSI_Node* First)
{
  SSI_Node* loc;
  SSI_Node* Temp;
  aType aTemp;
  if(First == 0)
  {
    loc = Top;
  }
  else
  {
    loc = First;
  }
  
  if(!loc) return 0;

  Temp = loc;
  while(Temp)
  {
    Temp->Get(aTemp);
    if(aTemp == inData) return Temp;
    Temp = Temp->next();
  }

  Temp = loc;
  while(Temp)
  {
    if(Temp->fchild())
    {
      loc = find(inData, Temp->fchild());
      if(loc) return loc;
    }
    Temp = Temp->next();
  }
  return 0;
}

template<class aType>
SSI_Node* TNodeTree<aType>::getTop()
{
  return Top;
}
//#pragma warning( default : 4251 )  // Disable warning messages


#endif



